package com.java.tree;

/**
 * 二叉树
 * 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，
 * 或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 * 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树
 * @author 19252
 * @date 2020/7/23
 */
public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode heroNode1 = new HeroNode(1, "宋江");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义");
        HeroNode heroNode3 = new HeroNode(3, "吴用");
        HeroNode heroNode4 = new HeroNode(4, "公孙胜");
        HeroNode heroNode5 = new HeroNode(5, "关胜");
        HeroNode heroNode6 = new HeroNode(6, "林冲");
        HeroNode heroNode7 = new HeroNode(7, "秦明");
        HeroNode heroNode8 = new HeroNode(8, "呼延灼");
        System.out.println("添加操作！");
        binaryTree.addNode(heroNode5);
        binaryTree.addNode(heroNode2);
        // 添加去重测试
        /*binaryTree.addNode(heroNode2);
        binaryTree.addNode(heroNode1);
        binaryTree.addNode(heroNode3);
        binaryTree.addNode(heroNode4);
        binaryTree.addNode(heroNode7);
        binaryTree.addNode(heroNode6);
        binaryTree.addNode(heroNode8);*/
        System.out.println("前序遍历！");
        binaryTree.preOrder();
        System.out.println("中序遍历！");
        binaryTree.infixOrder();
        System.out.println("后序遍历！");
        binaryTree.afterOrder();
        /* System.out.println("前序查找！");
        System.out.println(binaryTree.preOrderSearch(2));
        System.out.println("中序查找！");
        System.out.println(binaryTree.infixOrderSearch(2));
        System.out.println("后序查找！");
        System.out.println(binaryTree.afterOrderSearch(2));*/

        System.out.println("删除结点测试");
        binaryTree.deleteNode(5);
        binaryTree.deleteNode(2);
        System.out.println("再次中序遍历！");
        binaryTree.infixOrder();

    }
}

class BinaryTree {

    /**
     * 二叉树的根节点
     */
    HeroNode root;

    public HeroNode getRoot() {
        return root;
    }

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    /**
     * 向二叉树中添加结点
     * 按照大小顺序向二叉树中添加结点左边为小于该结点的结点，右边为大于该结点的结点
     *
     * @param node 二叉树的结点
     */
    public void addNode(HeroNode node) {
        HeroNode temp = this.root;
        if (temp == null) {
            this.root = node;
        } else {
            while (true) {
                // 重复添加判断
                if (node.getNo() == temp.getNo()) {
                    System.out.printf("您要添加的 %d 结点已存在！\n", temp.getNo());
                    break;
                }
                // 当前要添加的结点小于root结点，则向左添加
                if (node.getNo() < temp.getNo()) {
                    // 当前的结点的左子结点不为空
                    if (temp.getLeft() != null) {
                        // 就将当前节点变为当前结点的左子结点
                        // 再重新开始比较
                        temp = temp.getLeft();
                    } else {
                        // 完成加入树的操作退出
                        temp.setLeft(node);
                        break;
                    }
                } else {
                    // 当前要添加的结点大于等于root结点，则向右添加
                    if (temp.getRight() != null) {
                        temp = temp.getRight();
                    } else {
                        temp.setRight(node);
                        break;
                    }
                }

            }
        }
    }

    /**
     * 递归删除结点
     * 1. 如果删除的是叶子结点，则删除该结点
     * 2.如果删除的是非叶子结点，则在删除该结点的同时按照排序规则补足删除的结点位置
     *
     * @param no 被删除的结点编号
     */
    public void deleteNode(int no) {
        HeroNode temp = this.root;
        if (temp == null) {
            System.out.println("二叉树为空，没有数据可供删除！");
        } else {
            if (temp.getNo() == no) {
                if (temp.getLeft() == null) {
                    this.root = temp.getRight();
                    return;
                }
                if (temp.getLeft() != null) {
                    HeroNode right = temp.getRight();
                    this.root = temp.getLeft();
                    // 因为二叉树添加结点的规则是左小右大
                    this.root.getLastRightNode().setRight(right);
                    return;
                }
            }
            temp.deleteNode(no);
        }
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空！");
        }
    }

    public HeroNode preOrderSearch(int no) {
        return this.root.preOrderSearch(no);
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空！");
        }
    }

    public HeroNode infixOrderSearch(int no) {
        return this.root.infixOrderSearch(no);
    }

    /**
     * 后序遍历
     */
    public void afterOrder() {
        if (this.root != null) {
            this.root.afterOrder();
        } else {
            System.out.println("二叉树为空！");
        }
    }

    public HeroNode afterOrderSearch(int no) {
        return this.root.afterOrderSearch(no);
    }

}

/**
 * 树的结点
 *
 * @author 19252
 * @date 2020/7/23
 */
class HeroNode {

    /**
     * no 排名
     */
    private int no;

    /**
     * 姓名
     */
    private String name;

    /**
     * 左结点
     */
    private HeroNode left;

    /**
     * 右结点
     */
    private HeroNode right;

    public HeroNode() {
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 删除结点并补全
     *
     * @param no 被删除结点的no
     */
    public void deleteNode(int no) {
        // 根节点已经被预处理（根节点没有父结点，不能按下面的逻辑处理）
        HeroNode temp = this;
        // 当前节点的左结点是被删除的结点
        if (temp.getLeft() != null && temp.getLeft().getNo() == no) {
            // left 此时就是需要被删除的结点
            HeroNode left = temp.getLeft();
            // 判断被删除的结点是否有两个子结点
            if (left.getLeft() == null && left.getRight() == null) {
                // 没有直接置空
                temp.setLeft(null);
            }
            // 如果被删除的结点存在右结点，将该右结点上升补全
            else if (left.getLeft() == null && left.getRight() != null) {
                temp.setLeft(left.getRight());
            }
            // 如果被删除的结点只存在左节点就直接将左节点上升补全
            else if (left.getLeft() != null && left.getRight() == null) {
                temp.setLeft(left.getLeft());
            }
            // 左右都存在，就将被删除结点的右结点挂载到左节点的最下层的右结点上
            else if (left.getLeft() != null && left.getRight() != null) {
                left.getLeft().getLastRightNode().setRight(left.getRight());
                temp.setLeft(left.getLeft());
            }
            // 结束删除
            return;
        }

        // 当前节点的右结点是被删除的结点
        if (temp.getRight() != null && temp.getRight().getNo() == no) {
            // right 此时就是需要被删除的结点
            HeroNode right = temp.getRight();
            // 如果right 没有左右结点，直接置空
            if (right.getLeft() == null && right.getRight() == null) {
                temp.setRight(null);
            }
            // 如果 right 只存在右结点，将该右结点上升补全
            else if (right.getLeft() == null && right.getRight() != null) {
                temp.setRight(right.getRight());
            }
            // 如果 right 只存在左结点，将该左结点上升补全
            else if (right.getLeft() != null && right.getRight() == null) {
                temp.setRight(right.getLeft());
            }
            // 如果左右结点都存在，将right 的右结点挂载到左结点的最后右结点上
            else if (right.getLeft() != null && right.getRight() != null) {
                right.getLeft().getLastRightNode().setRight(right.getRight());
                temp.setRight(right.getLeft());
            }
            // 删除查找结束
            return;
        }
        // 向左递归删除查找
        if (temp.getLeft() != null) {
            temp.getLeft().deleteNode(no);
        }
        // 向有递归查找
        if (temp.getRight() != null) {
            temp.getRight().deleteNode(no);
        }
    }

    /**
     * 获取该结点下的最后一个右结点
     *
     * @return 返回一个结点下的最后一个右结点
     */
    public HeroNode getLastRightNode() {
        HeroNode temp = this;
        while (temp.getRight() != null) {
            temp = temp.getRight();
        }
        // 子二叉树最下层的最右边的结点
        return temp;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.getLeft() != null) {
            this.getLeft().preOrder();
        }
        if (this.getRight() != null) {
            this.getRight().preOrder();
        }
    }

    /**
     * 前序查找
     *
     * @param no 被查找的编号
     * @return 返回被查找到的HeroNode 对象
     */
    public HeroNode preOrderSearch(int no) {
        System.out.println("前序查找！~~~");
        if (this.getNo() == no) {
            return this;
        }
        HeroNode result = null;
        // 左递归查询
        if (this.getLeft() != null) {
            result = this.getLeft().preOrderSearch(no);
        }
        // 先判断左递归查找是否找到结果
        if (result != null) {
            return result;
        }
        // 没找到在向右递归查找
        if (this.getRight() != null) {
            result = this.getRight().preOrderSearch(no);
        }
        // 直接返回查找结果
        return result;
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.getLeft() != null) {
            this.getLeft().infixOrder();
        }
        System.out.println(this);
        if (this.getRight() != null) {
            this.getRight().infixOrder();
        }
    }

    /**
     * 中序查找
     *
     * @param no 查找的no
     * @return 返回被查找到的HeroNode 对象
     */
    public HeroNode infixOrderSearch(int no) {
        HeroNode result = null;
        if (this.getLeft() != null) {
            result = this.getLeft().infixOrderSearch(no);
        }
        // 左递归的null 判断
        if (result != null) {
            return result;
        }
        System.out.println("中序查找！~~~");
        if (this.getNo() == no) {
            return this;
        }
        if (this.getRight() != null) {
            result = this.getRight().infixOrderSearch(no);
        }
        return result;
    }

    /**
     * 后序遍历
     */
    public void afterOrder() {
        if (this.getLeft() != null) {
            this.getLeft().afterOrder();
        }
        if (this.getRight() != null) {
            this.getRight().afterOrder();
        }
        System.out.println(this);
    }

    /**
     * 后序查找
     *
     * @param no 查找的no
     * @return 返回被查找到的HeroNode 对象
     */
    public HeroNode afterOrderSearch(int no) {
        HeroNode result = null;
        if (this.getLeft() != null) {
            result = this.getLeft().afterOrderSearch(no);
        }
        if (result != null) {
            return result;
        }
        if (this.getRight() != null) {
            result = this.getRight().afterOrderSearch(no);
        }
        System.out.println("后序查找！~~~");
        if (this.getNo() == no) {
            return this;
        }
        return result;
    }
}

